import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * User: user
 * Date: 22.03.13
 * Time: 14:45
 * To change this template use File | Settings | File Templates.
 */
public class BinaryTree {
    private Node root;

    private static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(Node left, Node right, int value) {
            this.left = left;
            this.right = right;
            this.value = value;
        }

        public Node(int value) {
            this.value = value;
            left = null;
            right = null;
        }

    }

    public BinaryTree(Node root) {
        this.root = root;
    }

    public BinaryTree() {
        this.root = null;
    }

    public void insert(int val){
        root = insert(root, val);
    }

    private Node insert(Node node, int value) {
        if (node==null) {
            node = new Node(value);
        }
        else {
            if (value <= node.value) {
                node.left = insert(node.left, value);
            }
            else {
                node.right = insert(node.right, value);
            }
        }

        return(node);
    }

    public void delete(int val) {
        root = delete(root, val);
    }

    private Node delete(Node node, int value) {
        if  (value == node.value) {
            node = null;
        }
        else if (value < node.value) {
            node.left = delete(node.left, value);
        }
        else {
            node.right = delete(node.right, value);
        }

        return(node);
    }

    public void printVertical(){
        System.out.println("Vertical print:");
        printVertical(root);
    }

    public void printHorisontal(){
        System.out.println("Horisontal print:");
        printHorisontal(root);
    }

    private void printHorisontal( Node node){
        if (node.left != null) printHorisontal(node.left);
        if (node.right != null) printHorisontal(node.right);
        System.out.print(node.value + " ");
    }

      private void printVertical(Node root){
        Queue<Node> level  = new LinkedList<Node>();
        level.add(root);
        while(!level.isEmpty()){
            Node node = level.poll();
            System.out.print(node.value + " ");
            if(node.left!= null)
                level.add(node.left);
            if(node.right!= null)
                level.add(node.right);
        }
    }

   public static void main (String [] args ){
               BinaryTree tree = new BinaryTree();
       tree.insert(5);
       tree.insert(4);
       tree.insert(3);
       tree.insert(7);
       tree.insert(6);
       tree.insert(1);
       tree.printHorisontal();
       tree.printVertical();
       tree.delete(4);
       tree.printHorisontal();
       tree.printVertical();
   }

}
